package zip;

import static zip.Utils.*;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

import zip.HuffZip.Node;

public class HuffUnzip {
	public static void main(String[] args) {
		String path = "D:\\workspace\\Java workspace\\lanJie\\src\\zip\\tests\\test.txt.huff";
		doUnzip(path);
	}

	private static Queue<Node> pq = null; // priorityQueue用于构造Huffman树时排序
	private static int[] freq = null; // 记录每个字符的出现次数
	private static Map<String, Integer> map = null; // 用于解码时映射字符的ASCII值
	private static Node root = null; // Huffman树根
	private static int bytesCount; // 用于记录一共有多少有效字符
	private static final int CHS = 300; // 总的字符种类有256个

	/**
	 * 读入要解压的文件
	 * 
	 * @param pathName 文件路径
	 */
	public static void doUnzip(String pathName) {
		initUnzip();
		StringBuffer buffer = new StringBuffer(), temp = new StringBuffer();
		String key = null;
		File inFile = new File(pathName);
		File outFile = new File(pathName.substring(0, pathName.length() - ".txt".length()));
		DataInputStream din = null;
		DataOutputStream dout = null;

		try {
			din = new DataInputStream(new FileInputStream(inFile));
			dout = new DataOutputStream(new FileOutputStream(outFile));
			bytesCount = to(din.readByte());
			// System.out.println("bytes count = " + bytesCount);
			for (int i = 0; i < bytesCount; ++i) {
				byte ch = din.readByte();
				freq[to(ch)] = din.readInt();
				// System.out.println(to(ch) + " " + ch + ":" + freq[to(ch)] + "  ");
			}
			// System.out.println("");
			createTree();
			int extraBitsCount = to(din.readByte());
			// System.out.println("extra bits counter = " + extraBitsCount);

			while (true) {
				byte bits = din.readByte();
				buffer.append(toBuffer(bits));

				findChar: while (true) {
					boolean find = false;
					temp.delete(0, temp.length());
					for (int i = 0; i < buffer.length() - extraBitsCount; ++i) {
						temp.append(buffer.charAt(i));
						key = new String(temp);
						if (map.containsKey(key)) {
							find = true;
							dout.write(map.get(key));
							buffer.delete(0, temp.length());
							break;
						}
					}
					if (!find)
						break findChar;
				}
			}
		} catch (IOException ioe) {
			try {
				din.close();
				dout.close();
			} catch (IOException e) {
				System.out.println("closing din dout errors");
			}
			// System.out.println("the Output File Size = " + outFile.length());
			inFile = null;
			outFile = null;
		}
	}

	private static void initUnzip() {
		pq = new PriorityQueue<>();
		freq = new int[CHS];
		map = new HashMap<>();
		root = null;
		bytesCount = 0;
	}

	/**
	 * 构建huffman树
	 */
	private static void createTree() {
		if (bytesCount == 0)
			return;
		for (int i = 0; i < CHS; ++i) {
			if (freq[i] > 0) {
				Node node = new Node(null, null, freq[i]);
				node.key = i;
				pq.add(node);
			}
		}
		while (pq.size() > 1) {
			Node temp1 = pq.poll(), temp2 = pq.poll();
			Node fath = new Node(temp1, temp2, temp1.freq + temp2.freq);
			pq.add(fath);
		}
		root = pq.poll();
		setHash(root, "");
		// System.out.println("total value = " + root.freq);
	}

	/**
	 * 构建hash表，用于解码查询
	 * 
	 * @param root 哈夫曼树根
	 * @param code root的编码
	 */
	private static void setHash(Node root, String code) {
		if (root == null)
			return;
		if (root.left == null && root.right == null) {
			map.put(code, root.key);
		}
		setHash(root.left, code + "0");
		setHash(root.right, code + "1");
	}
}
